
class Solution {
    //创建一个辅助数组
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int left, int right) {
        //首先处理边界情况
        //区间不存在，或者只有一个元素
        if (left >= right) {
            return;
        }
        //先选择中间点划分区间
        int mid = (left + right) / 2;
        //[left,mid] [mid + 1,right]
        //相当于二叉树的后序遍历
        //先处理左边
        mergeSort(nums, left, mid);
        //在处理右边
        mergeSort(nums, mid + 1, right);
        //接下来就要进行合并数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            //首先执行 nums[cur1] <= nums[cur2]
            //如果 为真 将tmp[i++] = nums[cur1++]
            //否则 tmp[i++] = nums[cur2++]
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = nums[cur2++];
        }
        //还原
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
    }
}

public class Test01 {

}
